import org.w3c.dom.Node;

import javax.swing.tree.TreeNode;
import java.util.*;

public class Leetcode {
}

//leetcode:429:N叉树的层序遍历
class Solution1 {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int cnt = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < cnt; i++ ) {
                Node node = q.poll();
                tmp.add(node.val);
                for (Node cur : node.children) {
                    q.offer(cur);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
}

//leetcode:103:二叉树的锯齿形层序遍历
//方法一：队列
class Solution2 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 1;
        while (!q.isEmpty()) {
            int cnt = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < cnt ; i++) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            //如果在偶数行就将值进行翻转
            if(level % 2 == 0) Collections.reverse(tmp);
            ret.add(tmp);
            level++;
        }
        return ret;
    }
}

//方法二：双栈
class Solution3 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(root);
        Stack<TreeNode> stack2 = new Stack<>();
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            if(!stack1.isEmpty()){
                while(!stack1.isEmpty()){
                    TreeNode cur = stack1.pop();
                    if(cur.left != null) stack2.push(cur.left);
                    if(cur.right != null) stack2.push(cur.right);
                    tmp.add(cur.val);
                }
            } else if (!stack2.isEmpty()) {
                while(!stack2.isEmpty()){
                    TreeNode cur = stack2.pop();
                    if(cur.right != null) stack1.push(cur.right);
                    if(cur.left != null) stack1.push(cur.left);
                    tmp.add(cur.val);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
}
